package cn.jolyoulu.common.core.algorithms.tree.biarysorttree;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.function.Consumer;

/**
 * @Author LuZhouJin
 * @Date 2022/6/24
 * 顺序二叉树节点
 */
@Data
@AllArgsConstructor
@NoArgsConstructor
public class Node<T extends Comparable<T>> {
    private T value;
    private boolean tail;
    private Node<T> left;
    private Node<T> right;

    public Node(T value) {
        this.value = value;
    }

    public Node(T value, boolean tail) {
        this.value = value;
        this.tail = tail;
    }

    //递归添加节点添加
    public void add(Node<T> node) {
        if (node == null) {
            return;
        }
        //传入节点与当前节点值比较
        if (node.value.compareTo(this.value) < 0) {
            //如果当前左子节点空，直接添加
            if (this.left == null) {
                this.left = node;
            } else { //否则进行向左边找
                this.left.add(node);
            }
        } else {
            //如果当前右子节点空，直接添加
            if (this.right == null) {
                this.right = node;
            } else { //否则进行向右边找
                this.right.add(node);
            }
        }
    }


    //查找节点
    public Node<T> search(T value) {
        if (value.compareTo(this.value) == 0) { //找到了就返回
            return this;
        } else if (value.compareTo(this.value) < 0) { //如果比当前节点小往左子树找
            //如果左子节点为空，表示找不到
            if (this.left == null) {
                return null;
            }
            return this.left.search(value);
        } else {
            //如果右子节点为空，表示找不到
            if (this.right == null) {
                return null;
            }
            return this.right.search(value);
        }
    }

    //查找节点父节点
    public Node<T> searchParent(T value) {
        if ((this.left != null && this.left.value.compareTo(value) == 0)
                || (this.right != null && this.right.value.compareTo(value) == 0)) { //找到了就返回
            return this;
        } else {
            //如果查找值小于当前节点，并且当前节点左子节点不空，向左子树递归查找
            if (value.compareTo(this.value) < 0 && this.left != null) {
                return this.left.searchParent(value);
                //如果查找值大于当前节点，并且当前节点右子节点不空，向右子树递归查找
            } else if (value.compareTo(this.value) >= 0 && this.right != null) {
                return this.right.searchParent(value);
                //没有父节点(例：root节点)
            } else {
                return null;
            }
        }
    }

    //中序遍历二叉树
    public void infixOrder(Consumer<Node<T>> consumer) {
        if (this.left != null) {
            this.left.infixOrder(consumer);
        }
        consumer.accept(this);
        if (this.right != null) {
            this.right.infixOrder(consumer);
        }
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("Node{");
        sb.append("value=").append(value);
        sb.append('}');
        return sb.toString();
    }
}
